We provide a systematic method for nonlinear entanglement detection based on trace polynomial inequalities. In particular, this allows us to employ multipartite witnesses for the detection of bipartite states, and vice versa. We identify pairs of entangled states and witnesses for which linear detection fails, but for which nonlinear detection succeeds. With the trace polynomial formulation a great variety of witnesses arise from immanant inequalities, which can be implemented in the laboratory through the randomized measurements toolbox.