The message-passing principle is used in the most popular neural networks for graph-structured data. However, current message-passing approaches use black-box neural models that transform features over continuous domain, thus limiting the reasoning capability of GNNs. Traditional neural networks fail to model reasoning over discrete variables.In this work, we explore a novel type of message passing based on a differentiable satisfiability solver. Our model learns logical rules that encode which and how messages are passed from one node to another node. The rules are learned in a relaxed continuous space, which renders the training process end-to-end differentiable and thus enables standard gradient-based training. Our experiments show that MaxSAT-GNN learns arithmetic operations and that is on par with state-of-the-art GNNs, when tested on graph structured data.