Nach dem Planungsauftrag im April 2002 wurde die Vorplanungsphase Entscheidungsunterlage-Bau (ES-Bau) durch den BBL M-V Geschäftsbereich Neubrandenburg in Eigenleistung erstellt, in einem Pilotprojekt durch den Bundesrechnungshof planungsbegleitend geprüft und im Februar 2003 haushaltsmäßig anerkannt. Im März 2004 erfolgte die Genehmigung der ES-Bau mit Gesamtkosten von rund 4,5 Millionen Euro. Nach Erarbeitung der Ausführungsunterlagen wurde im Juli 2004 mit den vorbereitenden Maßnahmen der Baufeldfreimachung der eigentliche Baubeginn vollzogen.

Das nicht unterkellerte, barrierefrei ausgestattete Gebäude besteht aus einem dreigeschossigen Hauptbau, der die gesamten allgemeinen und spezifischen Lehrsäle mit ihren Nebenfunktionen aufnimmt und einem eingeschossigen Anbau als Multifunktionsgebäude. Durch das Entwurfsprinzip einer klaren Zonierung der Lehrsäle (Nordseite) und dienenden Bereiche (Südseite) konnte eine gleichmäßige natürliche Belichtung der Großräume erreicht und auf Maßnahmen zum Sonnenschutz weitgehend verzichtet werden.
Neben allgemeinen Lehrsälen befinden sich in den Geschossen Fachbereiche für Kriminalistik mit Situationskabinetten, Sprachunterricht und Schulung Informationstechnik.
Durch verschiebbare Trennwandsysteme lassen sich mehrere Lehrsäle unterschiedlichen Bedürfnissen anpassen. Das Multifunktionsgebäude lässt sich damit in drei kleinere oder einen 260 m² großen Saal verwandeln.

Im Februar 2005 wurde durch den Geschäftsbereich Neubrandenburg ein künstlerischer Ideenwettbewerb ausgelobt, der durch ein bekletterbares Kunstwerk ("Adler") im Außenbereich eine Identifikationsfigur und ein Zeichen für das AFZ-O schaffen sollte, das über seinen künstlerischen Wert hinaus auch als Sportgerät mit dem Charakter eines Unikats nutzbar sein sollte. Das Preisgericht prämierte die Arbeit des Künstlers Jürgen Kümmel, die mittlerweile schon bergsteigerisch bezwungen wurde.