หลังรับราชการในกองทัพ กุสตาฟ เชาได้รับการติดต่อให้ทำหน้าที่ก่อตั้งและควบคุมดูแลงานตำรวจนครบาล และงานตำรวจภูธร โดยกุสตาฟ เชา ยินดีรับทำเพียงงานเดียว คือ การก่อตั้งกิจการตำรวจภูธร โดยกรมหลวงดำรงราชานุภาพ (พระอิสริยยศในขณะนั้น) เสนาบดีว่าการกระทรวงมหาดไทย ได้กราบบังคมทูลและทรงพระกรุณาโปรดเกล้าฯ ให้ตั้ง "กรมตำรวจภูธร" ขึ้น ในปี พ.ศ. 2440[7] แทนกรมกองตระเวนหัวเมือง และได้แต่งตั้งให้ พันเอกกุสตาฟ เชา หรือ หลวงศัลวิธานนิเทศ มาเป็นเจ้ากรม

ในการเริ่มต้นก่อตั้งสถานีตำรวจภูธร กุสตาฟ เชาได้จัดวางอัตรากำลังสำหรับสถานีตำรวจแต่ละแห่งไว้ 250 นาย มีนายตำรวจระดับผู้บังคับบัญชาทั้งชาวสยามและเดนมาร์ก โดยกระจายสถานีตำรวจออกไปในแต่ละท้องที่ประมาณ 400 สถานี ซึ่งต้องใช้กำลังตำรวจร่วมหมื่นนาย เนื่องจากต้องการกำลังพลจำนวนมาก เจ้ากรมตำรวจภูธรจึงรายงานความเห็นและขออนุมัติจากกระทรวงมหาดไทยเพื่อจัด ตั้งโรงเรียนสำหรับผลิตนายตำรวจขึ้นเอง ในปี พ.ศ. 2444 จึงได้มีการจัดตั้งโรงเรียนนายร้อยตำรวจภูธรขึ้นที่จังหวัดนครราชสีมา[8] ในบริเวณที่ราชการให้ชื่อว่า"ประตูชัยณรงค์" ซึ่งเดิมชาวเมืองเรียกกันว่า "ประตูผี" (ปัจจุบันคือที่ตั้งกองบัญชาการตำรวจภูธรภาค 3) ไปก่อน แล้วจึงค่อยย้ายไปในที่ที่เหมาะสมต่อไป

ในฐานะของเจ้ากรมตำรวจภูธร กุสตาฟ เชาถือได้ว่าเป็นเจ้านายที่ลูกน้องรัก ได้รับความเคารพนับถือในความสามารถด้วย ไม่ว่าจะเป็นความสามารถในการบริหารจัดการองค์กร ความมองการณ์ไกล ความยุติธรรม เหนือสิ่งอื่นใด คือ พลังงานในการทำงานที่ล้นเหลือ ความทุ่มเทของพระยาวาสุเทพ เจ้ากรมตำรวจภูธรนี้ เป็นเหตุผลหนึ่งที่ทำให้หน่วยงานตำรวจภูธรถือเป็นหน่วยงานที่มีผลงานดีเยี่ยมที่สุดหน่วยงานหนึ่งในยุคนั้น