We propose a random access scheme named coded frameless ALOHA to completely eliminate the inherent error floor of the original frameless ALOHA, and show the optimized performance of the system. Coded frameless ALOHA uses erasure correcting codes, and transmitted packets are retrieved by an iterative process between successive interference cancellation and a message-passing decoder for erasure correcting codes. The packet loss rate of coded frameless ALOHA is theoretically analyzed and used to optimize parameters so that the achievable throughput is maximized. Numerical examples show that the proposed scheme exhibits better performance than conventional frameless ALOHA schemes.