Colored Node Kayles is a combinatorial game played on an undirected graph \(G=(V,E)\) with vertex colors from black, gray, white. Two players, Black and White, alternate turns: Black selects a gray or black vertex, while White selects a gray or white vertex. The chosen vertex and its neighbors are then removed from G. The game continues until no valid moves remain, with the last player able to move declared the winner. Node Kayles, the special case of Colored Node Kayles with only gray vertices, has been extensively studied. Due to its simplicity and generality, results for Node Kayles have been applied to a broad range of other combinatorial games, though the partisan variant Colored Node Kayles has received far less attention. A restricted version, called Bigraph Node Kayles, was implicitly introduced by Schaefer in his seminal 1978 work, where one side of a bipartite graph is colored black and the other white. We formally define Colored Node Kayles and study the complexity of deciding the winner. We prove that it is PSPACE-complete even on planar graphs with maximum degree 3. We also show W[1]-hardness with respect to the number of turns and present other hardness results, including for computing game values. On the algorithmic side, Colored Node Kayles is FPT concerning graph structural parameters such as clique deletion number, neighborhood diversity, vertex cover, and twin cover, and is solvable in polynomial time on graphs with bounded vertex integrity or cluster deletion number.