พื้นที่บริเวณตัวเมืองเซมุนปัจจุบันนั้นมีการตั้งรกรากมาตั้งแต่สมัยก่อนคริสตกาล โดยมีบันทึกครั้งแรกเกี่ยวกับการตั้งถิ่นฐานของชาวเคลต์กลุ่ม Scordisci ซึ่งต่อมาได้ถูกอาณาจัดรโรมันเอาชนะในสงครามขยายดินแดนและกลายเป็นส่วนหนึ่งของโรมันในที่สุด โดยชื่อชุมชนที่ถูกบันทึกไว้เป็นครั้งแรกคือเทารุนุม(อังกฤษ: Taurunum) โดยในยุคสมัยนั้นเมืองซินกิดุนุม (เขตเมืองเก่าของกรุงเบลเกรดในปัจจุบัน) มีฐานะเป็นป้อมปราการหลักแห่งหนึ่งของโรมันในภูมิภาคแพนโนเนียน ส่วนเทารุนุมนั้นก็เป็นที่ประจำการของกองเรือโรมันที่ทำการลาดตระเวนแม่น้ำดานูบใต้การบัญชาของกองทหารโรมันที่ประจำการที่ซินกิดุนุม

ในกาลต่อมา ครั้นเกิดการรุกรานยุโรปครั้งใหญ่ของกลุ่มชาวฮันในช่วงปี ค.ศ. 441 เทารุนุมและซินกิดุนุมต่างก็ถูกทำลายเสียหายจนสิ้นสภาพเมืองปราการที่เจริญใหญ่โตของโรมัน ขณะที่ช่วงปี ค.ศ. 500 กว่าๆเป็นต้นไป ทางซินกิดุนุมจะถูกทางโรมันเอากลับคืนไปแล้วเริ่มก่อสร้างเพื่อฟื้นสภาพเมือง เทารุนุมที่อยู่อีกฝั่งของแม่น้ำซาวานั้นต้องผจญกับการต่อสู้แย่งชิงดินแดนของชนกลุ่มต่างๆ ทั้ง ชาวแฟรงก์ ออสโตรกอท ลอมบาร์ด อาวาร์ เป็นเวลานับหลายร้อยปี ก่อนที่จะถูกรวมเข้าเป็นส่วนหนึ่งของราชอาณาจักรฮังการีเป็นครั้งแรกตั้งแต่ปลายคริสต์ศตวรรษที่ 9 แต่กระนั้นภูมิภาคนี้ก็ยังเป็นสมรภูมิสามฝ่ายระหว่างราชอาณาจักรฮังการี อาณาจักรบัลกาเรีย และ อาณาจักรไบแซนไทน์ ที่ช่วงชิงการมีอิทธิพลในทั้งเซมลิน(บัลแกเรีย: Земльн; อังกฤษ: Zemlyn)(ชื่อในเวลานั้นของเซมุน) และเบลกราด(ชื่อภาษาสลาฟอันเป็นที่มาของชื่อเบลเกรด)

ปี ค.ศ. 1096 เชมลินได้ถูกบันทึกไว้ในประวัติศาสตร์ยุโรปอีกครั้งเมื่อกองทัพชาวบ้านและชาวนาจากฝรั่งเศสและเยอรมันที่ออกเดินทางมาเองภายใต้การนำของ Peter the Hermit ซึ่งเรียกกันว่า People's Crusade เพื่อจะไปร่วมรบในสงครามครูเสดครั้งที่ 1 ได้เดินทางมาถึงเซมลินโดยได้รับการอนุญาตจากกษัตริย์ของฮังการีให้ผ่านดินแดนเข้ามาได้ก่อนเข้าสู่เขตแดนของไบแซนไทน์เพื่อเดินทางต่อไป ทว่าเมื่อเดินทางมาถึง กลุ่มชาวบ้านซึ่งไม่มีระเบียบวินัยเยี่ยงทหารและขาดการควบคุมได้ไปก่อความวุ่นวายขึ้นในตลาดของเมืองและถูกทหารฮังการีซึ่งประจำการอยู่ในเมืองจับกุมและยึดอาวุธ จึงเกิดความเข้าใจผิดขึ้นและนำไปสู่การจลาจลโดยฝั่งชาวบ้านที่จะรบในสงครามครูเสดได้ทำการเผาเมืองเซมลินและฆ่าชาวเมืองและทหารไปเป็นจำนวนมากก่อนจะหลบหนีกองทัพของฮังการีที่ยกกำลังตามมาเพื่อจัดการ โดยหนีข้ามแม่น้ำซาวาไปยังเบลกราดและก่อเหตุในลักษณะเดิมอีกครั้ง จากเหตุที่เกิดขึ้นทำให้ในบันทึกเกี่ยวกับการเดินทางโดยกลุ่มชาวบ้านนั้นขนานนามเรียกเซมลินว่า เมืองแห่งความชั่วร้าย (อังกฤษ: Malevilla)