กองทหารนี้อาจก่อตั้งขึ้นในอิตาลีในช่วงปี 48 ก่อนคริสต์ศักราช จูเลียส ซีซาร์ ซึ่งต้องการกองทหารนี้ในการทำสงครามกับปอมเปย์ [ ^{2 ] กอง} ทหารนี้ ได้เข้าร่วมการรบครั้งแรกในยุทธการที่ดิร์ราเคียมหลังจากสงครามกลางเมือง กองทหารนี้ถูกประจำการในมาซิโดเนีย เดิมทีมีกำหนดจะเข้าร่วมในปฏิบัติการของซีซาร์ต่อต้านจักรวรรดิพาร์เธียอย่างไรก็ตาม การเดินทางครั้งนี้ถูกยกเลิกหลังจากซีซาร์เสียชีวิต กองทหารนี้ได้เข้าร่วมรบในสงครามกลางเมืองระหว่างแอนโทนีและออกัสตัสก่อนที่ความขัดแย้งจะปะทุขึ้น กองทหารนี้ถูกย้ายไปยังอิตาลีโดยมาร์ค แอนโทนีแม้ว่าสิ่งนี้จะไม่ทำให้พวกเขาเปลี่ยนใจจากการเข้าข้างออกัสตัส^{[ 2 ]}ในระหว่างยุทธการที่มูตินาซึ่งพวกเขาต่อสู้กับแอนโทนีและได้รับความสูญเสียอย่างหนัก^{[ 3 ] [ 4 ]}ในปี 42 ก่อนคริสต์ศักราช กองทหารนี้ได้เข้าร่วมรบในยุทธการที่ฟิลิปปีและกลับไปยังอิตาลีพร้อมกับออกัสตัส^{[ 5 ]}เกือบถูกทำลายในการรบที่ฟิลิปปี แต่ก็รอดมาได้และถูกสร้างขึ้นใหม่ ซึ่งน่าจะเป็นผลให้มีชื่อว่ามาซิโดเนีย [ ^{5 ] ต่อ}มาพวกเขาได้เข้าร่วมในการล้อมเมืองเปรูจาในฤดูหนาวปี 41 ก่อนคริสต์ศักราช ซึ่งลูเซียส อันโตนิอุส น้องชายของมาร์ค อันโตนี ได้ลี้ภัยอยู่ที่นั่น^{[ 3 ]}กองทหารนี้ยังเข้าร่วมในการรบที่แอคติอุมในปี 31 ก่อนคริสต์ศักราชด้วย^{[ 3 ]}

หลังจากออกัสตัสขึ้นเป็นจักรพรรดิ ในปี 30 ก่อนคริสต์ศักราช กองทัพถูกย้ายไปที่จูลิโอบริกาในฮิสปาเนีย ตาร์ราโคเนนซิสเพื่อต่อสู้ในสงครามแคนตาเบรียน^{[ 5 ]}หลังสงคราม ทหารยังคงรับราชการเป็นข้าราชการพลเรือนในฮิสปาเนียต่อไป^{[ 3 ]}

จักรพรรดิคลอเดียสอาจย้ายกองทหารไปที่ไมนซ์ในเยอรมาเนียซูพีเรียร์เพื่อแทนที่กองทหารเจมินาที่ 14 ^{[ 3} ] ^{[ 6 ]น่าจะ}เป็นในปี ค.ศ. 41 อย่างไรก็ตาม บางคนคิดว่ากองทหารถูกย้ายในปี ค.ศ. 39 เมื่อจักรพรรดิคาลิกูลาทำสงครามกับชาวเยอรมันแชตติขณะที่ประจำการอยู่ในเยอรมาเนีย กองทหารที่ 4 ได้ใช้ป้อมปราการร่วมกับกองทหาร พริมิเจเนีย ที่ 22 ที่ เพิ่งก่อตั้งขึ้น หน่วยที่อายุน้อยกว่าได้ประจำการอยู่ทางด้านซ้ายมือซึ่งไม่ค่อยมีเกียรติ ในขณะที่กองทหารมาซิโดเนียที่ 4 อาศัยอยู่ทางด้านขวามือ^{[ 3 ]}

ในช่วงปีแห่งจักรพรรดิสี่พระองค์กองทัพที่สี่เป็นหนึ่งในกองทัพแรกๆ ที่เข้าข้างวิเทลลิอุสทหารของกองทัพนี้ได้เข้าร่วมในการเดินทัพของวิเทลลิอุสไปยังอิตาลี พวกเขาได้พิชิตเส้นทางผ่านสวิตเซอร์แลนด์ต่อสู้ที่เครโมนาและเบเดรียคัมกับกองทัพของจักรพรรดิโอโธทหารหลายคนได้รับรางวัลสำหรับการรับใช้ของพวกเขา^{[ 3 ]}ต่อมาพวกเขาพ่ายแพ้ต่อ เวส ปาเซียน^{[ 5 ]}

ในขณะเดียวกัน ในเยอรมาเนียอินเฟอริออร์ ชาวบาตาเวียนได้ก่อกบฏในระหว่างการกบฏ กองทัพมาซิโดเนียที่ 4 ได้ปกป้องเมืองไมนซ์จากการโจมตีของชาวเยอรมันอย่างแชตตีอุซิเพเตสและมัตติอาซีแม้ว่าจะประสบความสำเร็จในระหว่างการรบ แต่จักรพรรดิองค์ใหม่ก็ยังมองกองทัพนี้ด้วยความสงสัย ด้วยเหตุนี้ กองทัพจึงถูกลงโทษ ถูกจัดตั้งใหม่ภายใต้ชื่อใหม่ว่า กองทัพฟลาเวียเฟลิกซ์ที่ 4 และได้รับสัญลักษณ์ใหม่คือสิงโต^{[ 3 ] [ 7 ] [ 8 ]}สิงโตมีความเกี่ยวข้องกับเฮอร์คิวลีสเทพเจ้าที่เวสปาเซียนโปรดปราน^{[ 5 ]}

กองทหารโรมันที่ 4 มา ซิโดเนีย (Legio IV Macedonica) ใหม่ถูกย้ายไปยังเบอร์นุม (Burnum)ซึ่งเป็นค่ายทหารโรมันในดัลมาเทีย (Dalmatia ) กองทหารนี้จะอยู่ที่นั่นจนถึงปี ค.ศ. 70 ในปี ค.ศ. 85 กองทหารนี้ถูกย้ายไปยังซิงกูดูนุม (Singudunum ) ในโมเอเซีย (Moesia ) กองทหารนี้ยังถูกย้ายไปยังซีเรีย ด้วย ^{[ 9 ]}โดยนายพลคอร์บูโล (Corbulo ) ^{[ 10 ]}ในรัชสมัยของโดมิเทียน (Domitian) กองทหาร นี้ได้ต่อสู้กับชาวอเลมมานี (Alemmani) และชาวดาเซีย (Dacians)ต่อมาได้เข้าร่วมในสงครามดาเซียของทราจัน (Trjan ) กองทหารโรมันที่ 4 มาซิโดเนีย (Legio IV Macedonica) จะอยู่ที่ซิงกูดูนุมเป็นเวลา 200 ปี หลังจากนั้นก็หายไปจากประวัติศาสตร์^{[ 5 ]}