Sachverhalt: A. Die Z._ AG beabsichtigt, auf der Parzelle Nr. 2961 an der Adresse L._ in Lostorf eine UMTS-Mobilfunkanlage zu errichten. Der sichtbare Teil der geplanten Antennenanlage besteht aus einem sechs Meter hohen Mast mit Pipe-Antenne und Richtfunkantenne auf dem Flachdach eines bestehenden Gebäudes. Mit Verfügung vom 29. August 2011 entschied die Baukommission Lostorf, die ersuchte Baubewilligung für die Mobilfunkanlage nicht zu erteilen. Das Bau- und Justizdepartement des Kantons Solothurn hiess eine von der Z._ AG dagegen erhobene Verwaltungsbeschwerde am 7. September 2012 gut und erteilte die Baubewilligung für die geplante Anlage unter Auflagen und Bedingungen. Gegen den Entscheid des Bau- und Justizdepartements erhoben die Einwohnergemeinde Lostorf und X._ je Verwaltungsgerichtsbeschwerde an das Verwaltungsgericht des Kantons Solothurn, welches die Beschwerden mit Urteil vom 1. März 2013 abwies, soweit es darauf eintrat. B. Gegen das Urteil des Verwaltungsgerichts vom 1. März 2013 hat X._ am 8. April 2013 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Er beantragt, das angefochtene Urteil sei aufzuheben und die ersuchte Baubewilligung nicht zu erteilen bzw. das Baugesuch der Z._ AG abzuweisen. Eventualiter sei die Sache zur Prüfung von Alternativstandorten an die Baukommission zurückzuweisen. C. Mit Verfügung vom 13. Mai 2013 hat der Präsident der I. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde die aufschiebende Wirkung zuerkannt. Die Vorinstanz und die Beschwerdegegnerin beantragen, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Das Bau- und Justizdepartement beantragt Beschwerdeabweisung. Das zur Vernehmlassung eingeladene Bundesamt für Umwelt (BAFU) kommt zum Schluss, der angefochtene Entscheid stehe im Einklang mit der Umweltgesetzgebung des Bundes. Der Beschwerdeführer und die Beschwerdegegnerin haben im weiteren Schriftenwechsel an ihren Anträgen festgehalten. 