Zgodnie z hitlerowską polityką centralizacji rozgrywki piłkarskie podlegały centralnemu urzędowi jakim był Urząd ds. Piłki Nożnej (Fachamt Fuβball; pełna nazwa brzmiała: Fachamt 2 – Fußball, Rugby, Kricket) będący częścią Niemieckiego Związku Rzeszy ds. Ćwiczeń Fizycznych (Reichsbund für Leibesübungen). Efektem tej centralizacji było utworzenie w 1933 roku Gauligi – scentralizowanego systemu rozgrywek piłkarskich o mistrzostwo Niemiec, które składały się z dwóch rund:
rundy regionalnej – rozgrywanej w Okręgach Rzeszy (Gau)
rundy centralnej – gdzie zwycięzcy okręgów rywalizowali między sobą.
Gauliga Ostpreußen zrzeszała zespoły z Prus Wschodnich i Wolnego Miasta Gdańsk, będącego pod kontrolą Ligi Narodów. Zastąpiła Bezirksligi (najwyższe klasy rozgrywkowe w Cesarstwie Niemiec i Republice Weimarskiej) należące do Baltischer Sport-Verband, czyli Bałtyckiego Związku Sportowego, który organizował mistrzostwa w prowincjach Prus Wschodnich (Ostpreußen), Prus Zachodnich (Westpreußen), a od roku 1913 także Pomorza (Pommern), które jednak w roku 1933 stało się odrębnym okręgiem z własną ligą (Gauliga Pommern).
W skład Gauligi Ostpreußen początkowo weszło 14 drużyn, podzielonych na dwie grupy. Rozgrywały one w sezonie 12 spotkań w systemie każdym z każdym (jeden mecz u siebie, jeden na wyjeździe). Zwycięzcy obu grup rozgrywali pomiędzy sobą mecz finałowy dwumecz, wyłaniający mistrza ligi, który kwalifikował się on do Mistrzostw Niemiec. Z kolei ostatni zespół z każdej grupy, spadł z ligi. Taki system obowiązywał do sezonu 1934/1935.
Od sezonu 1935/1936 Gauliga Ostpreußen była podzielona na cztery grupy według okręgów: Allenstein, Danzig, Gumbinnen oraz Königsberg. W skład każdej wchodziło 7 klubów. Dwa najlepsze z każdej grupy kwalifikowały się do rundy finałowej, w której brało udział 8 zespołów, podzielonych na dwie grupy. Podobnie jak w poprzednich sezonach, zwycięzcy obu grup rozgrywali pomiędzy mecz o mistrzostwo ligi.
W 1938 roku doszło do reorganizacji rozgrywek, polegającej na połączeniu wszystkich czterech grup Gauligi w jedną dywizję i zmniejszeniu liczby drużyn uczestniczących w rozgrywkach z 28 do 10. W 1939 roku z powodu coraz bardziej restrykcyjnej polityki nazistów, klub polskiej mniejszości, Gedania Gdańsk, musiał zrezygnować z występów w lidze i został rozwiązany.
Od sezonu 1940/1941 w Gaulidze Ostpreußen występowało 7 drużyn. Rozgrywki w tym systemie funkcjonowały do sezonu 1943/1944, który okazał się ich ostatnim. W 1944 roku z powodu przemarszu Armii Czerwonej przez tereny Prus Wschodnich, liga nie wystartowała. W styczniu 1945 miała miejsce Operacja wschodniopruska, która całkowicie pochłonęła ten rejon działaniami wojennymi. Z kolei w maju 1945 teren Prus Wschodnich został podzielony pomiędzy Polskę i ZSRR i przestał być terenem Rzeszy.
