Handling public complaints of Probolinggo city, known as “Laporo Rek”, requires more time to provide the report to the relevant office. Its caused by the administrators sometimes doesn't know where the Public complaints to addressed. Using the naïve Bayes algorithm in Text Mining for Public Complaints of Probolinggo city can help the administrators to work more effectively and efficiently. The processing data of Public Complaints of Probolinggo city through several stages of text mining, which are token, filter, steaming, and analyzing. After completed the stage, the data will be classified using the naïve Bayes algorithm. The naïve Bayes algorithm calculation will view the result of each data class of Public Complaints of Probolinggo city, which is entered by phone, text message complaints. The research using this method has resulted in accuray 95%; it means each public complaints of Probolinggo city can be classified by each government agency in Probolinggo.