The non-unicost Set Covering Problem is a well-known NP-hard problem with many practical applications. In this work, a new approach based on Binary Firefly Algorithm is proposed to solve this problem. The Firefly Algorithm has attracted much attention and has been applied to many optimization problems. Here, we demonstrate that is also able to produce very competitive results solving the portfolio of set covering problems from the OR-Library.