Designing novel unconventional computing systems often requires the selection of the computational structure as well as choosing the right symbol encoding. Several approaches apply heuristic search and evolutionary algorithms to find both computational structure and symbol encoding, which is time consuming because they depend on each other. Here, we present a novel approach that combines evolution with self-organization, in particular we evolve the computational structure but let the symbol encoding emerge through self-organization. This should not only be more efficient but should also lead to a more �natural� symbol encoding. We successfully demonstrate the potential of the technique, using an evolutionary algorithm to optimize the parameters of two non-linear media to perform as NAND-gates: a continuous-time recurrent neural network (CTRNN) and a computational model of BZ-droplet-based computing (DropSim). In both cases, the technique identified representations for TRUE and FALSE, and system configurations that performed successfully as NAND-gates. The effectiveness of the evolved NAND gates was further evaluated by their performance in half-adder networks, where again, both evolved systems performed correctly, producing the correct output for all possible inputs and for all possible transitions between inputs. We conclude that beyond the specific applications demonstrated here, combining evolution with self-organization could be a promising strategy widely applicable.