Short Message Service is usually used to transport unclassified information, but with the rise of mobile commerce it has become an integral tool for conducting business. However, SMS does not guarantee confidentiality and integrity of the message content. This paper proposes a protocol called SMSSec that can be used to secure an SMS communication sent by Java's Wireless Messaging API. The physical limitations of the intended devices such as mobile phones, made it necessary to develop a protocol which would make minimal use of computing resources. SMSSec has a two-phase protocol with the first handshake using asymmetric cryptography which occurs only once, and a more efficient symmetric nth handshake which is used more dominantly. What distinguishes this work from conventional protocols is the ability to perform the secure transmission with limited size messages. Performance analysis showed that the encryption speed on the mobile device is faster than the duration of the transmission. To achieve security in the mobile enterprise environment, this is deemed a very acceptable overhead. Furthermore, a simple mechanism handles fault tolerance without additional overhead is proposed.