A number of recently discovered protein structures incorporate a rather unexpected structural feature: a knot in the polypeptide backbone. These knots are extremely rare, but their occurrence is likely connected to protein function in as yet unexplored fashion. Our analysis of the complete Protein Data Bank reveals several new knots which, along with previously discovered ones, can shed light on such connections. In particular, we identify the most complex knot discovered to date in human ubiquitin hydrolase, and suggest that its entangled topology protects it against unfolding and degradation by the proteasome. Knots in proteins are typically preserved across species and sometimes even across kingdoms. However, we also identify a knot which only appears in some transcarbamylases while being absent in homologous proteins of similar structure. The emergence of the knot is accompanied by a shift in the enzymatic function of the protein. We suggest that the simple insertion of a short DNA fragment into the gene may suffice to turn an unknotted into a knotted structure in this protein.