A new type of art image, called rectangle-based Neo-Plasticism-like image, is proposed, via which messages can be hidden for covert communication. Also proposed is an automatic method for creating such art images, which applies recursive binary partitioning to a source image by finding the maximum mutual information of the spatial positions and image intensities of the divided sub-regions. The resulting image consists of rectangular regions separated by horizontal and vertical lines, which show the abstraction style of the Neo-Plasticism art. Attracted by the artistic image content, a hacker hopefully will pay no attention to the hidden secret. Two data hiding techniques based on the binary partition tree constructed in the art image creation process are proposed, which embed messages by replacing the LSBs of each rectangular region’s colors or by generating additional partition lines in the region. A message extraction process is also proposed. Data security is considered seriously by randomizing the message bits before being embedded, changing randomly the priorities of the sub-regions used in message hiding, and embedding fake messages to interfere with the hacker. Good experimental results show the feasibility of the proposed techniques for covert communication via the proposed type of art image.