Over the past two decades, significant researches have been done in analyzing the MD5 algorithm to address its collision problem. This paper enhanced the original MD5 by adding four logical operations to increase the security of the message to become free from collision attack. To test the enhanced algorithm, different data with collision problems using the MD5 Collision generator were used. The avalanche effect was measured, and the result provided more than 50%-bit change. The enhanced MD5 was also tested against dictionary attack using online cracking tools and these tools failed to crack and revert the message digest into plain text. Overall, the enhanced algorithm mitigated the collision problem of MD5.