Los mensajes SMS se almacenan en la memoria interna del teléfono, por lo general en esta ubicación.
/data/data/com.android.providers.telephony/databases/mmssms.db
También, si usted ha instalado algunas aplicaciones, por defecto, las aplicaciones son instaladas en la memoria interna, a menos que se haya especificado lo contrario ans estás usando Froyo o superior, o alguna otra variante de Apps2SD etc.
Puede utilizar una aplicación como SMS de Copia de seguridad y archivo de SMS en tu cuenta de Gmail o una alternativa de aplicación SMS como GoSMS que tiene una disposición para copia de seguridad/restauración de SMS de la Tarjeta SD.
Como un aparte, intente liberar un poco de espacio moviendo / desinstalación de aplicaciones que no requieran y limpiar la caché del navegador y la aplicación de datos de otras aplicaciones. Una aplicación como Cachemate podría ayudar si usted tiene root.