เมื่อปี พ.ศ. 2520 เฉลิมวุฒิ ได้สวมเสื้อติดธงผืนแรกกับเยาวชนทีมชาติไทยชุดชนะเลิศแห่งอาเซี่ยน และสามารถพัฒนาฝีเท้าก้าวขึ้นสู่ทำเนียบทีมชาติชุดใหญ่ เมื่อ พ.ศ. 2522 เพื่อเดินทางไปแข่งขันฟุตบอล ปัค จุง ฮี คัพ (เพรสซิเด้นท์คัพ) ที่ ประเทศเกาหลีใต้ รายการเดียวกันปีต่อมา วันที่ 29 สิงหาคม พ.ศ. 2523 ทีมชาติไทย ชนะ ทีมมาเลเซีย 4-1 โดยเขาได้ทำประตูแรกในนามทีมชาติสำเร็จ และต่อมาในระหว่าง พ.ศ. 2528 และ พ.ศ. 2529 เฉลิมวุฒิ คือ กองกลาง ที่ฟอร์มการเล่นดีที่สุดใน ทีมชาติไทย จึงยึด ครองตำแหน่งกองกลางทีมชาติอย่างถาวร เพราะสไตล์การเล่นแบบใช้สมองและเปิดลูกที่แม่นยำ จนได้รับการขนานนามจากคอลูกหนังชาวไทยทั่วไปว่า มิดฟิลด์เท้าชั่งทอง ซึ่งเขาได้ร่วมรับใช้ทีมชาติกับ ปิยะพงศ์ ผิวอ่อน เพื่อนร่วมทีมชาติ โดยต่อมาในการแข่งขันฟุตบอลซีเกมส์ ครั้งที่ 13 รอบชิงชนะเลิศ ที่ สนามศุภชลาศัย วันที่ 17 ธันวาคม พ.ศ. 2528 ทีมชาติไทย ชนะ ทีมชาติสิงคโปร์ไป 2-0 นั้น ผู้ทำทั้ง 2 ประตูของเกม คือ เฉลิมพล โดยเขากล่าวหลังจบเกมส์การแข่งขันว่า โค้ชชาวเยอรมัน มร.โบการ์ด ซีเซ่ รู้ดีว่าทีมสิงคโปร์คงจะต้องวางแผนประกบ ปิยะพงษ์ ผิว อ่อน อย่างแน่นอน จึงมอบหน้าที่ให้ผมคอยหาจังหวะยิงประตูแทนและด้วยความช่วยเหลือของเพื่อน ๆ ผมทำได้สำเร็จนอกจากความภูมิใจ ที่สามารถช่วยให้ทีมไทยคว้าเหรียญทองในบ้านของเราเองแล้ว ยังทำให้เหรียญทองรวมของทีมนักกีฬาไทย ขึ้นเป็น ๙๓ เหรียญทอง ลบสถิติเก่าของอินโดนีเซียที่เคยทำเอาไว้อีกด้วย และ ในช่วงปลายชีวิตค้าแข้ง เฉลิมวุฒิในวัย 31 ปี ยังคงได้รับความไว้วางใจจาก มร.คาร์ลอส อัลเบอร์โต้ คาวัลโย โค้ชชาวบราซิลให้ติดทีมชาติลงเล่นฟุตบอลสี่เส้าอินโดจีน กรุงเทพ ฯ และสามารถนำทัพทีมไทยคว้าแชมป์มาครองสำเร็จ เมื่อเดือน ธันวาคม พ.ศ. 2532 และ ก่อนจะลงเล่นฟุตบอลชิงแชมป์มหาวิทยาลัย ให้กับมหาวิทยาลัยธรรมศาสตร์ เฉลิมวุฒิ ประสบอาการบาดเจ็บบริเวณหัวเข่า และเพื่อเปิดโอกาสให้นักเตะคนใหม่ให้ทดสอบตัวเองจึงทำให้ต้องขอถอนตัวจากทีมชาติชุดคิงส์คัพ ครั้งที่ ๒๑ ในปี พ.ศ. 2533 และ เมื่อไม่ถึง 1 เดือน เฉลิมวุฒิ ได้ประกาศแขวนสตั๊ดกับ ฟุตบอลทีมชาติไทย โดยเขาได้ลงรับใช้ให้ทีมชาติ 176 นัด ทำประตูได้ 18 ประตู