Die Ortskommandantur 258 (OK 258) wurde am 17. Juli 1941 in Oppeln, im Wehrkreis VIII, aufgestellt. Der Stab wurde nach der Aufstellung im Osten als Heerestruppe eingesetzt. Dabei wurde der Stab dem Befehlshaber Heeresgebiet Süd unterstellt. Von diesem wurde der Stab bei der 213. Sicherungs-Division eingesetzt. 1941 wurde der Stab in Piaseczno stationiert. 1942 ist der Stab in Lukow verzeichnet. 1942 unterstand der Stab dem Befehlshaber Heeresgebiet A. 1942/43 war der Stab in Osts stationiert. 1943 unterstand der Stab der 17. Armee. In diesem Jahr wurde der Stab in Labinskaja stationiert. Zuletzt unterstand der Stab 1945 der 9. Armee.

Die Ersatzgestellung des Stabes wurde durch das Infanterie-Ersatz-Bataillon 327, später Grenadier-Ersatz-Bataillon 327, wahrgenommen.