We analyze BPS equations for string-like configurations derived from the M5-brane worldvolume action with a Nambu-Poisson structure constructed in arXiv:0804.3629, arXiv:0805.2898. We solve the BPS equations up to the first order in the parameter $g$ which characterizes the strength of the Nambu-Poisson bracket. We compare our solutions to previously constructed BPS string solitons in the conventional description of M5-brane in a constant three-form background via Seiberg-Witten map, and find agreement.