محرم فوتبال خود را از تیم فوتبال سپاهان آغاز کرد. در سال ۱۳۷۷ توسط مهدی مناجاتی به تیم بزرگسالان سپاهان آمد. در نیم فصل دوم ۱۳۷۹ توسط حمید ندیمیان برای اولین بار در ترکیب فیکس تیم قرار گرفت. در سال 1381 پس از قهرمانی تیم ملی امید که نویدکیا در ترکیب آن فیکس بازی می کرد و بازگشتش از بوسان با اینکه از همه هم تیمی هایش کم سن تر بود با پیشنهاد آرمناک پطروسیان، لئون استپانیان و مجید بصیرت و با رضایت فرهاد کاظمی بازوبند کاپیتانی تیم به عنوان هدیه به او داده شد که تا امروز بر بازوی اش بسته است. وی در سال ۱۳۸۳ به باشگاه بوخوم پیوست؛ در ماه‌های اول حضورش درخشش خوبی داشت ولی بعدها با مصدومیت‌های همیشگی خودش روبرو شد و کم کم جایگاه خود را در ترکیب از دست داد و در اواخر سال ۱۳۸۵ به مدت چند ماه و قرضی به باشگاه سپاهان بازگشت و در اول فصل بعد قراردادش را دائمی کرد. نویدکیا در دومین دوره لیگ برتر برای نخستین‌بار قهرمانی با سپاهان را تجربه کرد و به عنوان جوان‌ترین کاپیتان لیگ جام قهرمانی را بالای سر برد. در لیگ نهم نیز که سپاهان با امیر قلعه‌نویی به قهرمانی دست یافت، نویدکیا دومین بار طعم دلچسب قهرمانی را چشید. در لیگ دهم نیز یک بار دیگر نویدکیا به عنوان کاپیتان تیم قهرمان جام را بالای سر برد تا هت‌تریک قهرمانی وی به طور رسمی ثبت شود. در لیگ یازدهم نیز سپاهان با هدایت کرانچار به قهرمانی رسید، اما این بار هم کاپیتان سپاهان کسی به جز نویدکیا نبود. نویدکیا در مقام کاپیتانی تیم سپاهان چهار بار هم جام قهرمانی جام حذفی را در دوره های ۸۳-۱۳۸۲، ۸۵-۱۳۸۴، ۸۶-۱۳۸۵، ۹۲-۱۳۹۱ بالای سر برده است. او در لیگ قهرمانان آسیا ۲۰۰۷ به همراه تیم سپاهان اصفهان به مقام نایب قهرمانی رسید.