The Max-Cut problem is known to be NP-hard on general graphs, while it can be solved in polynomial time on planar graphs. In this paper, we present a fixed-parameter tractable algorithm for the problem on “almost” planar graphs: Given an n-vertex graph and its drawing with k crossings, our algorithm runs in time \(O(2^k(n+k)^{3/2} \log (n + k))\). Previously, Dahn, Kriege and Mutzel (IWOCA 2018) obtained an algorithm that, given an n-vertex graph and its 1-planar drawing with k crossings, runs in time \(O(3^k n^{3/2} \log n)\). Our result simultaneously improves the running time and removes the 1-planarity restriction.