Sachverhalt: A. B._ (Arbeitnehmer, Beschwerdegegner) arbeitete vom 1. Dezember 2003 bis am 31. Dezember 2014 für A._ (Arbeitgeber; Beschwerdeführer), einen Verein nach Art. 60 ZGB. Vom 20. Oktober 2013bis zur Auflösung des Vertrages konnte der Arbeitnehmer seiner Arbeit (nach seinen Angaben krankheitsbedingt) nicht mehr nachkommen. Per 1. August 2014 hatte der Arbeitgeber seinen Sitz von Olten nach U._ verlegt. B. Nach erfolgloser Schlichtungsverhandlung reichte der Arbeitnehmer am 19. August 2015 beim Richteramt Olten-Gösgen Klage ein und verlangte vom Arbeitgeber Fr. 20'165.50 (Ferienguthaben per 2013) nebst Zins. Nachdem der Arbeitgeber die örtliche Zuständigkeit bestritten hatte, fällte der Amtsgerichtspräsident am 6. Januar 2016einen Zwischenentscheid. Darin entschied er im Wesentlichen, auf die Klage werde eingetreten. Die dagegen vom Arbeitgeber erhobene Berufung wies das Obergericht des Kantons Solothurn mit Urteil vom 30. März 2016 ab (Dispositivziffer 1), erhob keine Kosten (Dispositivziffer 2) und auferlegte ihm eine Parteientschädigung (Dispositivziffer 3). C. Mit Beschwerde in Zivilsachen beantragt der Arbeitgeber dem Bundesgericht, die Dispositivziffern 1 und 3 dieses Urteils aufzuheben, das Richteramt Olten-Gösgen anzuweisen, auf die Klage infolge fehlender örtlicher Zuständigkeit nicht einzutreten, und den Beschwerdegegner zu verpflichten, ihm für das kantonale Verfahren eine angemessene Parteientschädigung zu bezahlen. Eventualiter sei die Sache an das Obergericht zurückzuweisen. Der Beschwerdegegner beantragt, die Beschwerde kostenfällig abzuweisen. Auf eine eigentliche Vernehmlassung hat er verzichtet und erklärt, er halte an seinen Rechtsbegehren und seiner Sachverhaltsschilderung fest und schliesse sich den Ausführungen der kantonalen Instanzen an. Er weist darauf hin, alle Beweisanträge, die der Beschwerdeführer im Rahmen der Rechtsmittelverfahren gestellt habe, seien verspätet. Zu diesem Punkt hat der Beschwerdeführer eine Gegenbemerkung eingereicht. Das Obergericht beantragt unter Hinweis auf die Akten und die Motive des angefochtenen Urteils, die Beschwerde abzuweisen, und hat im übrigen auf eine Vernehmlassung verzichtet.