from matplotlib import pyplot as plt
fig, ax = plt.subplots()
ax.plot([0,1,2,3,4,5,6], label='linear')
ax.plot([0,1,4,9,16,25,36], label='square')
lgd = ax.legend(loc='lower right')
def add_patch(legend):
from matplotlib.patches import Patch
ax = legend.axes
handles, labels = ax.get_legend_handles_labels()
handles.append(Patch(facecolor='orange', edgecolor='r'))
labels.append("Color Patch")
legend._legend_box = None
legend._init_legend_box(handles, labels)
legend._set_loc(legend._loc)
legend.set_title(legend.get_title().get_text())
add_patch(lgd)
plt.show()